class Node {
  constructor(element, parent) {
    this.element = element;
    this.parent = parent;
    this.left = null;
    this.right = null;
  }
}
// 实现二叉搜索树
class BinarySearchTree {
  constructor(compare) {
    this.root = null;
    this.size = 0;
    this.compare = compare || this.compare;
  }
  compare(e1, e2) {
    return e1 - e2;
  }
  add(element) {
    if (this.root == null) {
      this.root = new Node(element, null);
      this.size++;
      return;
    } else {
      // 不是root节点，通过判断插入值的大小，区别插入左边还是右边
      let current = this.root;
      let compare = 0;
      let parent = null;
      while (current) {
        // compare = element - current.element;
        compare = this.compare(element, current.element);
        // 如果当前有元素，要继续向下层比较
        parent = current;
        if (compare > 0) {
          //  插入的值大，查找右树的元素作为当前节点【下次的root节点】，继续向下查找
          current = current.right;
        } else if (compare < 0) {
          // 否则查找左树
          current = current.left;
        } else {
          // 添加的元素已经存在
          current.element = element; //如果有重复的，用新的替换原来的
          return;
        }
      }
      // 左右都没有子元素给current赋值后，current为parent，为root，跳出while循环，
      let newNode = new Node(element, parent);
      if (compare > 0) {
        parent.right = newNode;
      } else {
        parent.left = newNode;
      }
    }
  }
}
let bst = new BinarySearchTree((e1, e2) => {
  return e1.age - e2.age;
});
// let arr = [10, 8, 19, 6, 15, 22, 20];
// 后边age为10的lisi会覆盖zs
let teams = [
  { age: 10, name: "zs" },
  { age: 8 },
  { age: 19 },
  { age: 6 },
  { age: 15 },
  { age: 22 },
  { age: 20 },
  { age: 10, name: "lisi" },
];
teams.forEach(function (element) {
  bst.add(element);
});
console.dir(bst.root, {depth:100});
